package com.hardy.leetcode;

/**
 * User: Ruijie Date: 2016/9/7
 */
public class AddTwoNumbers {

    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
            this.next=null;
        }
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null&&l2==null){
            return null;
        }
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode head1=l1;
        ListNode head2=l2;
        ListNode newHead=new ListNode(-1);
        ListNode head3=newHead;
        int carry=0;
        while(head1!=null&&head2!=null){
            int val=head1.val+head2.val;
            ListNode newNode=new ListNode((val+carry)%10);
            carry=(val+carry)/10;
            head3.next=newNode;
            head3=newNode;
            head1=head1.next;
            head2=head2.next;
        }
        printListNode(newHead);
        System.out.println("-------------");
        while(head1!=null){
            ListNode newNode=new ListNode((head1.val+carry)%10);
            carry=(head1.val+carry)/10;
            head3.next=newNode;
            head3=newNode;
            head1=head1.next;
        }
        while(head2!=null){
            ListNode newNode=new ListNode((head2.val+carry)%10);
            carry=(head2.val+carry)/10;
            head3.next=newNode;
            head3=newNode;
            head2=head2.next;
        }
        printListNode(newHead);
        System.out.println("-------------");
        if(carry>0){
            ListNode newNode=new ListNode(carry);
            head3.next=newNode;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode l1=new ListNode(2);
        l1.next=new ListNode(4);
        l1.next.next=new ListNode(3);
        ListNode l2=new ListNode(5);
        l2.next=new ListNode(6);
        l2.next.next=new ListNode(4);

        ListNode l3=new ListNode(1);
        ListNode l4=new ListNode(9);
        l4.next=new ListNode(9);
        ListNode node=addTwoNumbers(l3,l4);
        printListNode(node);
    }

    private static void printListNode(ListNode node) {
        ListNode pre=node;
        while(pre!=null){
            System.out.print(pre.val+" ");
            pre=pre.next;
        }
    }
}
